import java.util.ArrayList;
import java.util.List;

/**
 * Author: 笨蛋超人不会飞
 * Date:  20:35
 */
public class question_54 {
}
class Solution_54 {
    public List<Integer> spiralOrder(int[][] matrix) {
//        先进行特殊判断
        if(matrix==null||matrix.length==0){
            return null;
        }
        int row=matrix.length;
        int column=matrix[0].length;
        int arr[][]=new int[row][column];
        List<Integer> result=new ArrayList<>();
        int x_index=0;
        int y_index=0;
        while (true){
//            先是向右边添加
            for ( ; y_index <column ; y_index++) {
                result.add(matrix[x_index][y_index]);
//                表示是已经走过的了
                arr[x_index][y_index]=1;
                if(y_index+1==column||arr[x_index][y_index+1]==1){
//                    说明接下来要往下面走了
                    x_index=x_index+1;
                    break;
                }
            }
//            转折过程要加上判断
            if(x_index==row||arr[x_index][y_index]==1){
                break;
            }
//            向下面走
            for ( ; x_index <row ; x_index++) {
                result.add(matrix[x_index][y_index]);
//                标记是已经走过的了
                arr[x_index][y_index]=1;
                if(x_index+1==row||arr[x_index+1][y_index]==1){
//                    说明接下来要往左面走了
                    y_index=y_index-1;
                    break;
                }
            }
//            转折过程要加上判断
            if(y_index==-1||arr[x_index][y_index]==1){
                break;
            }
//            往左边
            for ( ; y_index >=0 ; y_index--) {
                result.add(matrix[x_index][y_index]);
//                表示是已经走过的了
                arr[x_index][y_index]=1;
                if(y_index-1==-1||arr[x_index][y_index-1]==1){
//                    说明接下来要往上面走了
                    x_index=x_index-1;
                    break;
                }
            }
//            转折过程要加上判断
            if(x_index==-1||arr[x_index][y_index]==1){
                break;
            }
//            往上
            for ( ; x_index >=0 ; x_index--) {
                result.add(matrix[x_index][y_index]);
//                表示是已经走过的了
                arr[x_index][y_index]=1;
                if(x_index-1==-1||arr[x_index-1][y_index]==1){
//                    说明接下来要往左面走了
                    y_index=y_index+1;
                    break;
                }
            }
//            转折过程要加上判断
            if(y_index==column||arr[x_index][y_index]==1){
                break;
            }
        }
        return result;
    }
//    官方的解答
public List<Integer> spiralOrder_2(int[][] matrix) {
    List<Integer> order = new ArrayList<Integer>();
//    考虑特殊的请款
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return order;
    }
    int rows = matrix.length, columns = matrix[0].length;
    boolean[][] visited = new boolean[rows][columns];
    int total = rows * columns;
    int row = 0, column = 0;
    int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int directionIndex = 0;
    for (int i = 0; i < total; i++) {
        order.add(matrix[row][column]);
        visited[row][column] = true;
        int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
        if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
            directionIndex = (directionIndex + 1) % 4;
        }
        row += directions[directionIndex][0];
        column += directions[directionIndex][1];
    }
    return order;
}



    public static void main(String[] args) {
        // 创建一个3行4列的二维数组
        int[][] array = new int[3][4];

        // 为数组元素赋值
        // 假设我们为数组赋值一个递增的序列
        int value = 1;
        // 从1开始赋值
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                array[i][j] = value++; // 为当前元素赋值，并递增value
            }
        }
        Solution_54 solution_54=new Solution_54();
        List<Integer> list = solution_54.spiralOrder(array);
        System.out.println(list);


    }
}
